package developer.算法.普通数组.合并区间;

import java.util.*;

/**
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 示例 2：
 * <p>
 * 输入：intervals = [[1,4],[4,5]]
 * 输出：[[1,5]]
 * 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
 */
public class HeBingQuJian {

    public static void main(String[] args) {
//        int[][] ints = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
//        int[][] ints = {{1, 4}, {4, 5}};
        int[][] ints = {{2, 3}, {2, 2}, {3, 4}, {5, 5}};
        int[][] merge = merge(ints);
        System.out.printf(Arrays.deepToString(merge));
    }


    //先排序  进行合并 然后添加到数组中
    public static int[][] merge(int[][] intervals) {
        Set<int[]> sortSet = new TreeSet<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        for (int[] interval : intervals) {
            sortSet.add(interval);
        }
        List<int[]> sortValues = new ArrayList<>(sortSet);
        int current = 0;
        List<int[]> result = new ArrayList<>();
        while (current < sortValues.size()) {
            int[] ints = sortValues.get(current);

            if (current == sortValues.size() - 1) {
                result.add(ints);
                break;
            }

            int end = ints[1];
            while (current < sortValues.size()) {
                if (current == sortValues.size() - 1) {
                    break;
                }
                int[] ints1 = sortValues.get(current + 1);
                int nextStart = ints1[0];
                int nextEnd = ints1[1];
                if (end >= nextStart) {//说明重合了  合并
                    end = Math.max(end, nextEnd);
                    ints[1] = end;
                    current++;
                } else {
                    break;
                }
            }
            result.add(ints);
            current++;

        }

        return result.toArray(new int[result.size()][]);


    }

    /**
     * 官方的做法是在 集合里面进行合并 也是一种思路
     */
    static class Solution {

        public int[][] merge(int[][] intervals) {
            if (intervals.length == 0) {
                return new int[0][2];
            }
            Arrays.sort(intervals, new Comparator<int[]>() {
                public int compare(int[] interval1, int[] interval2) {
                    return interval1[0] - interval2[0];
                }
            });
            List<int[]> merged = new ArrayList<int[]>();
            for (int i = 0; i < intervals.length; ++i) {
                int L = intervals[i][0], R = intervals[i][1];
                if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                    merged.add(new int[]{L, R});
                } else {
                    merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
                }
            }
            return merged.toArray(new int[merged.size()][]);
        }
    }

}
